#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void getSubArray2(int num[], int size, int sum)
{
    vector<int> preSum(size, num[0]);
    map<int, int> mp;

    for (int i = 1; i < size; i++)
        preSum[i] = preSum[i-1] + num[i];

    for (int i = 0; i < size; i++)
        cout << preSum[i] << " ";
    cout << endl;

    for (int i = 0; i < size; i++) {
        int need = preSum[i] - sum;
        if (mp.count(need) != 0) {
            cout << "Find : " << mp[need]+1 << " " << i << " " << preSum[i] << " " << need << endl;
            return;
        }
        mp[preSum[i]] = i;
    }
}

void getSubArray(int num[], int size, int sum)
{
    int curSum = num[0], start = 0, i;
    int maxSize = 0, maxStart = 0;

    for (i = 1; i < size; i++) {
        curSum += num[i];
        while(curSum > sum && start < i) {
            curSum -= num[start];
            start++;
        }
        if (curSum <= sum && i - start + 1 > maxSize) {
            maxSize = i - start + 1;
            maxStart = start;
        }
    }

    for (int i = 0; i < maxSize; i++) 
        cout << num[maxStart + i] << " ";
    cout << endl;
}

int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;
    int test1[] = {1, -2, 4, -2, 6, 7};
    getSubArray(test1, sizeof(test1)/sizeof(int), 7);

    cout << "-----------------Test 2--------------------" << endl;
    int test2[] = {1,1,1,1,-1};
    getSubArray(test2, sizeof(test2)/sizeof(int), 9);


    cout << "-----------------Test 3--------------------" << endl;
    int test3[] = {1,1,1,1,0,-1,0,-1,1};
    getSubArray(test3, sizeof(test3)/sizeof(int), 3);


    cout << "-----------------Test 4--------------------" << endl;
    int test4[] = {1,1,1,1,0,-1,0,1};
    getSubArray(test4, sizeof(test4)/sizeof(int), 3);

    cout << "-----------------Test 5--------------------" << endl;
    int test5[] = {1,1,100,-100,1};
    getSubArray(test5, sizeof(test5)/sizeof(int), 5);
}
